import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PalindromePartitioning {
    /*
    * 131. 分割回文串
    * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。
    * 返回 s 所有可能的分割方案。
    * 回文串 是正着读和反着读都一样的字符串。
    *
    * 1 <= s.length <= 16
    * s 仅由小写英文字母组成
    * */
    public static void main(String[] args){

    }

    // 我的想法：对s,从长度为1开始从头切割，判断是不是回文，如果是，则对剩余字串如法炮制，若不是，增加切割长度
    public List<List<String>> mySolution(String s){
        backtracking(s, 0);
        return res;
    }
    List<List<String>> res = new ArrayList<>();
    ArrayList<String> path = new ArrayList<>();
    private void backtracking(String s, int start){
        if(start == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int len = 1; len <= s.length() - start; len++) {
            int end = start + len;
            String sub = s.substring(start, end);
            if(isPalindrome(sub)){
                path.add(sub);
                backtracking(s, end);
                path.remove(path.size()-1);
            }
        }
    }

    private boolean isPalindrome(String s){
        int left = 0;
        int right = s.length()-1;
        while (left < right){
            if(s.charAt(left) != s.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }
}
